/*
 * @lc app=leetcode.cn id=1542 lang=cpp
 *
 * [1542] 找出最长的超赞子字符串
 */
#include <string>
#include <vector>
using namespace std;
// @lc code=start
class Solution
{
public:
    int longestAwesome(string s)
    {
        int max = 0;
        auto cache = vector<int>(1024, -1);
        cache[0] = 0;
        short counter = 0;
        for (int i = 0; i < s.length(); i++)
        {
            counter ^= 1 << (s[i] - '0');
            for (int j = 0; j < 10; j++)
            {
                short t = counter;
                t ^= 1 << j;
                // 查找
                if (cache[t] != -1)
                {
                    int tt = i + 1 - cache[t];
                    if (tt > max)
                    {
                        max = tt;
                    }
                }
            }
            if (cache[counter] != -1)
            {
                int tt = i + 1 - cache[counter];
                if (tt > max)
                {
                    max = tt;
                }
            }
            else
            {
                cache[counter] = i + 1;
            }
        }
        return max;
    }
};
// @lc code=end
